Asymmetrical key cryptography systems use pairs of keys, each pair comprises a public key and a private key, and each key may include a number of parameters. Each public key is linked to the identity of its holder by a certification authority. Asymmetrical key cryptography systems include entities known as controllers that store a number of public keys in conjunction with the certified identities of their holders.
The problem of factorizing integers has been the subject of intense research since the invention of the RSA asymmetrical key cryptographic method (see the article by M. Gardner, “A new kind of cipher that would take millions of years to break”, Scientific American, August 1977). The name RSA of the algorithm is derived from the initials of its inventors R. Rivest, A. Shamir, and L. Adleman. Despite considerable advances, more a result of growth in computing power than of progress in factorizing algorithms, there is still no known method of factorizing a large integer in a reasonable time. Users are therefore justified in placing their trust in the RSA method.
Each use of the RSA method is associated with an integer n known as the modulus and which is the product of two separate large prime factors p1 and p2. Given present-day computing capacities, it is recommended that moduluses of at least 1024 bits (of the order of 10308) are used. An RSA public key includes the modulus n and an exponent e that is prime with (p1−1) and with (p2−1). The corresponding RSA private key includes an exponent d such that (the symbol “mod” signifies “modulo”):e×d=1 mod[(p1−1)(p2−1)]
The security of this method relies on the fact that it is impossible to calculate d from n and e within a reasonable time if the factors p1 and p2 are not known. As explained above, it is not possible to calculate these factors (which are naturally kept secret) in a reasonable time.
The cryptographic procedure for entity authentication uses a controller and a keyholder, referred to below as the claimant, who wishes to be authenticated by the controller in order to receive an authorization, for example the authorization to access electronic data processing resources. The claimant declares an identity to the controller, and must prove to the controller that the claimant holds the private key corresponding to the public key linked to that identity.
It is possible to effect this authentication without the claimant disclosing to the controller any information at all concerning the claimant's private key: this technique is known as zero-knowledge proof authentication and is described in general terms by S. Goldwasser, S. Micali, and C. Rackoff in their paper “The Knowledge Complexity of Interactive Proof Systems” delivered at the 17th ACM Symposium on the Theory of Computing (Proceedings, 291 to 304, 1985).
In the paper “Zero-knowledge Proofs of Identity” (Journal of Cryptology, vol. 1, pages 77 to 94, 1988), U. Feige, A. Fiat, and A. Shamir propose a zero-knowledge proof cryptographic method in which the claimant holds a private key Q and publishes an RSA modulus n and a public key G=Q2 mod n (it is impossible to calculate Q from G, i.e. to calculate a square root modulo n, in a reasonable time unless the prime factors of n are known).
When the above method is applied to authenticating entities, the Fiat-Shamir procedure comprises the following interactive steps:
1. Witness step: the claimant chooses at random an integer r, calculates the “witness” R=r2 mod n and sends the witness to the controller;
2. Challenge step: the controller chooses at random an integer d called a “challenge” which can take the value 0 or the value 1 and sends the challenge to the claimant;
3. Response step: the claimant calculates the “response” D=r×Qd mod n and sends the response to the controller; and
4. Verification step: the controller calculates
      (                  D        2                    G        d              )    ⁢  mod  ⁢          ⁢  nand verifies that the result is equal to the witness R.
For increased security, it is recommended that this procedure should be repeated “sequentially” as many times as possible before considering that authentication has been effected (varying r and d each time).
This is a zero-knowledge proof procedure because an observer cannot calculate the private key Q of the claimant from the data exchanged.
In a Feige-Fiat-Shamir or parallel variant, the claimant holds a number m>1 of private keys Q1, Q2, . . . , Qm and publishes, in addition to an RSA modulus n, respective public keys G1, G2, . . . , Gm, where Gi=Qi2 mod n for i=1, . . . , m. The following steps are then executed:
1. Witness step: the claimant chooses at random an integer r, calculates the witness R=r2 mod n and sends the witness to the controller;
2. Challenge step: the controller chooses at random m challenges d1, d2, . . . , dm where di is equal to 0 or 1 and for i=1, . . . , m and sends the challenges to claimant;
3. Response step: the claimant calculates the response D=r×Q1d1×Q2d2× . . . ×Qmdm mod n and sends the response to the controller; and
4. Verification step: the controller calculates
      (                  D        2                              G          1                      d            1                          ×                  G          2                      d            2                          ×        …        ×                  G          m                      d            m                                )    ⁢  mod  ⁢          ⁢  nand verifies that the result is equal to the witness R.
This parallel variant accelerates the Fiat-Shamir authentication procedure compared to the sequential (i.e. series) variant referred to above.
Note further that the calculations required to implement either of these variants can be reduced if the claimant uses the Chinese remainder theorem well known to experts in number theory. The claimant may proceed in the following manner.
Consider first the calculation of the witness R. For a modulus n=p1×p2, where p1<p2, let a number C (known as a Chinese remainder) be the positive number less than p1 such that p1 is a factor of (p2×C−1). The claimant chooses at random two integers r1 and r2 such that 0<r1<p1 and 0<r2<p2 and calculates the two witness components R1=r12 mod p1 and R2=r22 mod p2. The value of the witness is deduced therefrom as follows, where z=C×(R1−R2):R=z×p2+R2 
To calculate the response D, the claimant may proceed as follows. Private key components Qi,1=Qi mod p1 and Qi,2=Qi mod p2 are defined for i=1, . . . , m. The claimant first calculates the two response components:D1=r1×Q1,1d1×Q2,1d2× . . . ×Qm,1dm mod p1, andD2=r2×Q1,2d1×Q2,2d2× . . . ×Qm,2dm mod p2.The claimant then obtains the value of the response as follows, where z=C×(D1−D2):D=z×p2+D2 
The advantage of this Chinese remainder calculation method is that the claimant calculates modulo p1 and modulo p2 instead of modulo n under conditions whereby p1 and p2 are generally much smaller than n.
The Fiat-Shamir entity authentication procedure may be transposed easily to verification by a controller that a message M that it has received was sent by a certain keyholder, here also called the claimant. This message authentication procedure comprises the following interactive steps:
1. Witness step: the claimant chooses at random an integer r and calculates first the witness R=r2 mod n and then the token T=h(M, R), where h is a hashing function (for example one of the functions defined in the ISO/IEC Standard 10118-3), and finally sends the token T to the controller;
2. Challenge step: the controller chooses at random a challenge d which can taken the value 0 or 1 and sends the challenge to the claimant;
3. Response step: the claimant calculates the response D=r×Qd mod n and sends the response to the controller; and
4. Verification step: the controller calculates
  h  ⁡      (          M      ,                        (                                    D              2                                      G              d                                )                ⁢        mod        ⁢                                  ⁢        n              )  and verifies that the result is equal to the token T.
Finally, the Fiat-Shamir entity authentication procedure can be transposed to define a procedure for signing a message M that is sent to a controller by a keyholder called the signatory; note that a signing procedure is not interactive in itself. The signatory holds a plurality of private keys Q1, Q2, . . . , Qm, where m is large compared to 1, and publishes, in addition to an RSA modulus n, respective public keys G1, G2, . . . , Gm where Gi=Qi2 mod n and for i=1, . . . , m. This signing procedure comprises the following steps (given the same names as above by analogy):
1. Witness step: the signatory chooses at random m integers ri where i=1, . . . , m and calculates first the witnesses Ri=ri2 mod n and then the token T=h(M, R1, R2, . . . , Rm), where h is a hashing function producing a word of m bits, and finally sends the token T to the controller;
2. Challenge step: the signatory identifies the bits d1, d2, . . . , dm of the token T;
3. Response step: the signatory calculates the responses Di=ri×Qidi mod n and sends the responses to the controller; and
4. Verification step: the controller calculates
  h  ⁡      (          M      ,                        (                                    D              1              2                                      G              1                              d                1                                              )                ⁢        mod        ⁢                                  ⁢        n            ,                        (                                    D              2              2                                      G              2                              d                2                                              )                ⁢        mod        ⁢                                  ⁢        n            ,      …      ⁢                          ,                        (                                    D              m              2                                      G              m                              d                m                                              )                ⁢        mod        ⁢                                  ⁢        n              )  and verifies that the result is equal to the token T.
Consider now in more detail the security of the Fiat-Shamir method. For example, in the case of the entity authentication procedure explained above, the question arises: is it possible for an impostor (i.e. an entity knowing the RSA modulus n and the public key G, but not knowing the private key Q of the entity that it is pretending to be) to fool the controller?
Note first that the challenge, although random, can take only two values: if an impostor guesses the value of the challenge thrown down by the controller during the authentication procedure correctly (and thus with a 50% chance of success), could it satisfy all the steps of the Fiat-Shamir method without being caught by the controller? The answer to this question is yes. In fact:                if the impostor guesses that the challenge will be d=0 it supplies to the controller a witness R=r2 mod n and a response D=r; and        if the impostor guesses that the challenge will be d=1 it chooses any integer l>0 and supplies to the controller a witness R=l2×G mod n and a response D=l×G mod n.        
The Fiat-Shamir procedure therefore has a weakness, although its effect can be attenuated, as indicated above, if the procedure is repeated sequentially to render a correct series of anticipations of the challenge by an impostor as improbable as possible. It follows that, to make this authentication procedure sufficiently secure, its duration must be considerably increased.
International application WO-00/45550 discloses a cryptography method that is applicable to an entity authentication procedure, a message authentication procedure and a message signing procedure and does not suffer from this drawback. In that method, the claimant publishes not only an RSA modulus n and a public key G but also an integer (called the exponent) v=2k where k (called the security parameter) is an integer greater than 1. Moreover, if Q is the private key of the claimant:G=Qv mod n  (1)
The authentication procedure of application WO-00/45550 comprises the following steps:
1. Witness step: the claimant chooses at random an integer r, calculates the witness R=rv mod n and sends the witness to the controller;
2. Challenge step: the controller chooses at random an integer d called the challenge, where 0≦d≦2k−1−1, and sends the challenge to the claimant;
3. Response step: the claimant calculates the response D=r×Qd mod n and sends the response to the controller; and
4. Verification step: the controller calculates
      (                  D        v                    G        d              )    ⁢  mod  ⁢          ⁢  nand verifies that the result is equal to the witness R.
Thus in this procedure the challenge can take 2k−1 different values (as opposed to only two values in the Fiat-Shamir method), which, for a single execution of the above succession of steps, makes correct anticipation of the challenge by an impostor increasingly improbable as the value of k increases.
This being the case, to enhance security, this procedure can of course be repeated sequentially s times and/or m pairs of keys can be used in parallel as explained above; it is then advantageous to use the Chinese remainder theorem for the calculations. In practice, because a hacker has more time to crack the code in the case of signing than in the case of authentication, it is recommended that the product [(k−1)×m×s] have a value at least equal to 40 in the case of authentication and at least equal to 80 in the case of signing.
Moreover, according to application WO-00/45550, the public key is required to satisfy the following relationship, in which g is a small integer (called the base number) greater than 1:G=g2 mod n  (2)
Combining the above equations (1) and (2) shows that it is necessary to find a pair (g, Q) satisfying the following equation for given n and v:Qv=g2 mod n  (3)
It can be shown that equation (3) can be solved in a reasonable time only by someone who knows the factors of the modulus, i.e. the keyholder. In other words, calculating a pair of keys conforming to application WO-00/45550 from the corresponding public parameters is just as complicated as factorizing the number n; the two tasks are said to be equivalent in terms of complexity and a set of keys implying this kind of equivalence satisfies the equivalence criterion.
A first advantage of this state of affairs is that there is a reference level of security (i.e. the factorization problem). A second advantage is that a holder of keys according to application WO-00/45550 does not need to have such a public key certified by a certification authority, i.e. to obtain from that authority a certificate linking that public key to the identity of its holder; it is only necessary to certify the RSA modulus n, the other parameters being published directly by the holder. In contrast, in the Fiat-Shamir method, for example, it is possible for different entities to construct their own pairs of keys from the same RSA modulus (Fiat-Shamir pairs therefore do not satisfy the equivalence criterion defined above), and consequently each particular public key must be linked by a certification authority to the identity of its holder.
It can nevertheless be shown that there exist solutions of equation (3) for only certain particular moduluses n (representing about one quarter of all RSA moduluses). This is problematic for an entity seeking to produce pairs of keys according to application WO-00/45550: if that entity already has a collection of RSA moduluses, it can generally use only some of them to construct the keys, whereas if it does not already have any RSA moduluses, it will find it more difficult to find adequate moduluses than if all (or almost all) the RSA moduluses were compatible with the method.